#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
// 128. 最长连续序列
// https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked-questions
// 给定一个未排序的整数数组 nums ，返回最长连续序列的长度。 
// 要求算法的时间复杂度为 O(n) 。
//
// 示例 1： 
// 输入：nums = [100,4,200,1,3,2]
// 输出：4
// 解释：最长连续序列是 [1, 2, 3, 4] ，其长度为 4。
// 示例 2：
// 输入：nums = [0,3,7,2,5,8,4,6,0,1]   
// 输出：9
// 解释：最长连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8] ，其长度为 9。


class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            
            int ans=0;
            unordered_set<int> st(nums.begin(),nums.end());
    
            for(int x:st)
            {
                if(st.contains(x-1))
                {
                continue;
                }
                int y=x+1;
                while(st.contains(y)){ //查找y在不在哈希集合里
                y++;}
    
                ans=max(ans,y-x);
            }
            return ans;
    
        }
    };

int main() {  
    Solution solution;
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    int result = solution.longestConsecutive(nums);
    cout << "The length of the longest consecutive sequence is: " << result << endl;
    return 0;
}
